package my.algorithm.sort;

import org.apache.commons.lang.ArrayUtils;

/**
 * 直接插入排序
 * @author xsw
 * @date 2018年9月27日
 */
public class DirectInsertSort {
	public static void main(String[] args) {
		int[] list = { 1,2 };
//		int[] list = { 6, 5, 3, 1, 8, 7, 2, 4 };
		System.out.println(ArrayUtils.toString(list));
		sort(list);
		System.out.println(ArrayUtils.toString(list));
	}
	/**
	 * 直接插入排序
	 * @param list 待排序集合
	 */
	public static void sort(int[] list){
		if(list == null || list.length == 0) return ;
		/**
		 * 1. 一列原始数据，从左到右排序，左边为已排序区，右边为待排序区
		 * 2. “待排序值”与左边已排序区做比较，插入到合适的位置
		 * 3. 直接插入排序采取循环遍历左边已排序区的方式来决定插入位置
		 */
		for (int i = 1; i < list.length; i++) {
			int temp = list[i];
			int j;
			//大于（小于）“待排序值”的都往右边复制
			for (j = i - 1; j >= 0; j--) {
				if(temp < list[j]){
					list[j+1] = list[j];
				}else{
					break;
				}
			}
			list[j+1] = temp;
		}
	}
}
